package com.example.Arithmetic.Arithmetic;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 日期：2023/12/27
 * 时间：11:27
 * 描述：快速排序，双边循环，随机数，重复数字
 * 选择最左侧元素作为基准点
 * j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换
 * i 从左向右
 * j 从右向左
 * 最后基准点与 i 交换，i 即为基准点最终索引
 */
public class QuickSortHoare {
    public void sort(int[] ints) {
        quick(ints, 0, ints.length - 1);
    }

    private void quick(int[] ints, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = partition(ints, left, right);
        quick(ints, left, i - 1);
        quick(ints, i + 1, right);
    }

    //    j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换
    private int partition(int[] ints, int left, int right) {
        int i1 = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(ints, i1, left);    // 获取随机数，不会出现极端情况

        int p = ints[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            // i 从左向右找大的或者相等的
            while (i <= j && ints[i] < p) {
                i++;
            }
            // j 从右向左找小的或者相等的
            while (i <= j && ints[j] > p) {
                j--;
            }
            if (i <= j) {
                swap(ints, i, j);
                i++;
                j--;
            }
        }
        swap(ints, j, left);
        return j;
    }

    public void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    @Test
    public void test() {
        int[] a = new int[1000000];
        int i = 0;

        Random random = new Random();
        while (i < 1000000) {
            int i1 = random.nextInt(100000000);
            a[i] = i1;
            i++;
        }
        System.out.println(Arrays.toString(a));
        QuickSortHoare quickSort = new QuickSortHoare();
        quickSort.sort(a);
        System.out.println("<===============================================================>");
        System.out.println(Arrays.toString(a));
    }
}
